package bin_tree.NewCoder;

import bin_tree.leetcode.TreeNode;

/**
 * @author shkstart
 * 将二分搜索树转为排序的双向链表
 *
 * @create 2022-10-26-23:10
 */
public class ConvertTree2LinkedList {
//    传入一个BST的根节点，将其转为双向链表，并返回链表头
    public TreeNode Convert(TreeNode pRootOfTree) {

//        边界
        if(pRootOfTree==null|| (pRootOfTree.left==null&&pRootOfTree.right==null)){
            return pRootOfTree;
        }

//        先转换左子树
        TreeNode left = Convert(pRootOfTree.left);
//        将左树的尾部与根节点连接
        TreeNode leftTail = left;
//        从头开始leftTail向后走，right相当于next
        while (leftTail != null && leftTail.right != null) {
            leftTail = leftTail.right;
        }
//        此时leftTail指向做链表的尾部
//        连接做链表尾部和根节点,right相当于next
        if (leftTail != null) {
            leftTail.right = pRootOfTree;
            pRootOfTree.left = leftTail;
        }
//        继续处理右子树
        TreeNode right = Convert(pRootOfTree.right);
//        将根节点和右树相连接
        if(right!=null){
            right.left = pRootOfTree;
            pRootOfTree.right = right;
        }
        return left==null?pRootOfTree:left;
    }
}
